package euler.helper;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PrimeHelper {

    private static boolean[] primos = new boolean[] {false,false,true,true,false,true,false,true,false,false};
    private static IncreasingPrimesHelper increasingPrimesHelper = new IncreasingPrimesHelper();

    public boolean isPrime(int n) {
        if (n < 2) {
            throw new IllegalArgumentException("Parametro " + n + " menor que 2");
        } else if (n > 982451653) {
        	return isNaivePrime(n);
        } else if (n >= 268435456) {
        	try {
        		return increasingPrimesHelper.isPrime(n);
			} catch (Exception e) {
				e.printStackTrace(System.out);
				return isNaivePrime(n);
			}
        }

        try {
        	return primoFromArray(n);
		} catch (OutOfMemoryError e) {
			e.printStackTrace(System.out);
			System.out.println("Out of memory for " + n);
			throw e;
		}
    }

    private boolean isNaivePrime(int i) {
    	if ((i % 2 == 0) || (i % 3 == 0) || (i % 5 == 0) || (i % 7 == 0)) {
            return false;
        } else {
            boolean isPrime = true;
            int sqrt = (int)Math.sqrt(i);
            for (int j = 11; isPrime && j <= sqrt; j+=2) {
            	isPrime = !(isPrime(j) && (i % j == 0));
            }
            return isPrime;
        }
	}

	private static boolean primoFromArray(int n) {
    	if (primos.length < n + 1) {
            int m = (int)Math.pow(2, (int)(Math.log(n)/Math.log(2)) + 1);
            boolean[] aux = new boolean[m];

            System.arraycopy(primos, 0, aux, 0, primos.length);

            for (int i = primos.length; i < aux.length; i++) {
            	aux[i] = increasingPrimesHelper.isPrime(i);
            }

            primos = aux;
        }

        return primos[n];
    }

    public long smallestFactor(long n) {
        if (n < 1) {
            throw new IllegalArgumentException("Parametro menor que 1");
        }

        if (n == 1) {
            return 1;
        } else if (n % 2 == 0) {
            return 2;
        } else if (n % 3 == 0) {
            return 3;
        } else if (n % 5 == 0) {
            return 5;
        } else if (n % 7 == 0) {
            return 7;
        }

        int i = 11;
        int sqrt = (int)Math.sqrt(n);
        while (i <= sqrt) {
            if (isPrime(i) && n % i == 0) {
                return i;
            }
            i+=2;
        }

        return n;
    }

    public long greatestFactor(long n) {
        if (n < 1) {
            throw new IllegalArgumentException("Parametro menor que 1");
        }

        long factor = 1;
        while (n != 1) {
            factor = smallestFactor(n);
            while (n % factor == 0) {
                n/=factor;
            }
        }

        return factor;
    }

    public List<Pair<Long,Integer>> factorizar(long n) {
        if (n < 1) {
            throw new IllegalArgumentException("Parametro menor que 1");
        }

        List<Pair<Long,Integer>> list = new ArrayList<Pair<Long,Integer>>();

        if (n == 1) {
            list.add(Pair.of(1l, 1));
        } else {
        	if (NaturalHelper.isSquare(n)) {
        		long sqrt = (long)Math.sqrt(n);
        		List<Pair<Long,Integer>> factoresRaiz = factorizar(sqrt);

        		for (Pair<Long, Integer> factor : factoresRaiz) {
        			list.add(Pair.of(factor.left, factor.right * 2));
				}
        	} else {
        		long oldFactor = 1;
                int exp = 0;

                while (n > 1) {
                    long factor = smallestFactor(n);

                    if (oldFactor != factor) {
                        if (oldFactor != 1) {
                            list.add(Pair.of(oldFactor, exp));
                        }
                        oldFactor = factor;
                        exp=1;
                    } else {
                        exp++;
                    }

                    n/=factor;
                }

                list.add(Pair.of(oldFactor, exp));
        	}
        }

        return list;
    }

    public List<Integer> divisores(long n) {
        if (n < 1) {
            throw new IllegalArgumentException("Parametro menor que 1");
        }

        List<Integer> list = new ArrayList<Integer>();
        list.add(1);

        if (n == 1) {
        	// Do nothing
        } else if (n < Integer.MAX_VALUE && isPrime((int)n)) {
            list.add((int)n);
        } else {
            List<Pair<Long,Integer>> factores = factorizar(n);

            for (Pair<Long,Integer> pair: factores) {
                long base = pair.left;
                int exp = pair.right;
                List<Integer> aux = new ArrayList<Integer>(list);
                for (int i=0; i<=exp; i++) {
                    for (int l: aux) {
                        int newV = l*(int)Math.pow(base, i);
                        if (!list.contains(newV)) {
                            list.add(newV);
                        }
                    }
                }
            }

            Collections.sort(list);
        }

        return list;
    }


    public long MCM(long x, long y) {
        return x*y/MCD(x, y);
    }


    public int cantidadDivisores(int n) {
        int i = 1;

        for (Pair<Long, Integer> p: factorizar(n)) {
            if (p.left > 1) {
                i*=(p.right + 1);
            }
        }

        return i;
    }

    public long MCD(long x, long y) {
        if (x < 1 || y < 1) {
            throw new IllegalArgumentException("Parametro menor que 1");
        }

        long b = Math.max(x, y);
        long a = Math.min(x, y);
        while (a > 0) {
            long c = b % a;
            b = a;
            a = c;
        }

        return b;
    }

    public boolean relativelyPrimes(int m, int n) {

        if ((m == 1) || (n == 1)) {
            return true;
        } else if ((m % n == 0) || (n % m == 0)) {
            return false;
        } else if (isPrime(m) || isPrime(n)) {
            return true;
        }

        return MCD(m, n) == 1;
    }

    public BigInteger MCD(BigInteger x, BigInteger y) {
        if (x.compareTo(BigInteger.ONE) < 0 || y.compareTo(BigInteger.ONE) < 0) {
            throw new IllegalArgumentException("Parametro menor que 1");
        }

        BigInteger b = x.max(y);
        BigInteger a = x.min(y);
        while (a.signum() > 0) {
            BigInteger c = b.remainder(a);
            b = a;
            a = c;
        }

        return b;
    }
}